/**
 * 
 */
package fhq.hcmute.qrcode.detector;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import fhq.hcmute.qrcode.common.BinaryImage;
import fhq.hcmute.qrcode.util.MathUtils;
import fhq.hcmute.qrcode.util.QRCodeException;
import fhq.hcmute.qrcode.util.MathUtils.MyVector;

/**
 * @author Hien Nguyen Le
 * @Email: nglehien@gmail.com
 */
public class FinderPatternFinder {
	private final BinaryImage image;
	private ArrayList<PatternPoint> listPoint;
	private static final int INTEGER_MATH_SHIFT = 8;

	public FinderPatternFinder(BinaryImage image) {
		this.image = image;
		listPoint = new ArrayList<PatternPoint>();
	}

	protected final BinaryImage getImage() {
		return image;
	}

	public final FinderPatternInfo find() throws QRCodeException {
		int maxI = image.getHeight();
		int maxJ = image.getWidth();
		int iSkip = 3;
		boolean done = false;
		int[] stateCount = new int[5];
		for (int i = iSkip - 1; i < maxI && !done; i += iSkip) {
			// Get a row of black/white values
			stateCount[0] = 0;
			stateCount[1] = 0;
			stateCount[2] = 0;
			stateCount[3] = 0;
			stateCount[4] = 0;
			int currentState = 0;
			for (int j = 0; j < maxJ; j++) {
				if (image.getPixel(i, j)) {
					// Black pixel
					if ((currentState & 1) == 1) { // Counting white pixels
						currentState++;
					}
					stateCount[currentState]++;
				} else { // White pixel
					if ((currentState & 1) == 0) { // Counting black pixels
						if (currentState == 4) { // A winner?
							if (checkRatios(stateCount)) { // Yes
								boolean confirmed = confirmFinderPattern(
										stateCount, i, j);
								if (!confirmed) {
									stateCount[0] = stateCount[2];
									stateCount[1] = stateCount[3];
									stateCount[2] = stateCount[4];
									stateCount[3] = 1;
									stateCount[4] = 0;
									currentState = 3;
									continue;
								}
								// Clear state to start looking again
								currentState = 0;
								stateCount[0] = 0;
								stateCount[1] = 0;
								stateCount[2] = 0;
								stateCount[3] = 0;
								stateCount[4] = 0;
							} else { // No, shift counts back by two
								stateCount[0] = stateCount[2];
								stateCount[1] = stateCount[3];
								stateCount[2] = stateCount[4];
								stateCount[3] = 1;
								stateCount[4] = 0;
								currentState = 3;
							}
						} else {
							stateCount[++currentState]++;
						}
					} else { // Counting white pixels
						stateCount[currentState]++;
					}
				}
			}
		}
		FinderPatternInfo finderPatternInfo = getBestFinderPattern();
		// getDegre(finderPatternInfo.getTopLeft(),
		// finderPatternInfo.getTopRight());
		return finderPatternInfo;
	}

	private FinderPatternInfo getBestFinderPattern() {
		if (listPoint.size() > 2) {
			// Sort by Matched
			Collections.sort(listPoint, new MatchedCount());
			listPoint.subList(3, listPoint.size()).clear();
			// Sort by Distance
			sortDistance(listPoint);
			return new FinderPatternInfo(listPoint);
		}
		return null;
	}

	private void sortDistance(ArrayList<PatternPoint> listPoint) {
		float distanceAToB = MathUtils.getDistance(listPoint.get(0),
				listPoint.get(1));
		float distanceAToC = MathUtils.getDistance(listPoint.get(0),
				listPoint.get(2));
		float distanceBToC = MathUtils.getDistance(listPoint.get(1),
				listPoint.get(2));

		PatternPoint p1;
		PatternPoint p2;
		PatternPoint p3;
		if (distanceBToC > distanceAToB && distanceBToC > distanceAToC) {
			p1 = listPoint.get(0);
			p2 = listPoint.get(1);
			p3 = listPoint.get(2);
		} else if (distanceAToB > distanceAToC && distanceAToB > distanceBToC) {
			p1 = listPoint.get(2);
			p2 = listPoint.get(0);
			p3 = listPoint.get(1);
		} else {
			p1 = listPoint.get(1);
			p2 = listPoint.get(2);
			p3 = listPoint.get(0);
		}

		MyVector vectorA = new MyVector(p2, p1);
		MyVector vectorB = new MyVector(p1, p3);
		if (MathUtils.crossVector(vectorA, vectorB) < 0) {
			PatternPoint temp = p2;
			p2 = p3;
			p3 = temp;
		}

		listPoint.set(0, p1);
		listPoint.set(1, p2);
		listPoint.set(2, p3);

	}

	private static float estimateCenter(int[] stateCount, int end) {
		return (float) (end - stateCount[4] - stateCount[3]) - stateCount[2]
				/ 2.0f;
	}

	protected static boolean checkRatios(int[] stateCount) {
		int totalModuleSize = 0;
		for (int i = 0; i < 5; i++) {
			int count = stateCount[i];
			if (count == 0) {
				return false;
			}
			totalModuleSize += count;
		}
		if (totalModuleSize < 7) {
			return false;
		}
		int moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;
		int maxVariance = moduleSize / 2;
		// Allow less than 50% variance from 1-1-3-1-1 proportions
		return Math.abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < maxVariance
				&& Math.abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < maxVariance
				&& Math.abs(3 * moduleSize
						- (stateCount[2] << INTEGER_MATH_SHIFT)) < 3 * maxVariance
				&& Math.abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < maxVariance
				&& Math.abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < maxVariance;
	}

	private float checkCrossVertical(int startI, int centerJ, int maxCount) {
		BinaryImage image = this.image;
		int maxI = image.getHeight();
		int[] stateCount = new int[5];

		// Start counting up from center
		int i = startI;
		while (i >= 0 && image.getPixel(i, centerJ)) {
			stateCount[2]++;
			i--;
		}
		if (i < 0) {
			return Float.NaN;
		}
		while (i >= 0 && !image.getPixel(i, centerJ)
				&& stateCount[1] <= maxCount) {
			stateCount[1]++;
			i--;
		}
		// If already too many modules in this state or ran off the edge:
		if (i < 0 || stateCount[1] > maxCount) {
			return Float.NaN;
		}
		while (i >= 0 && image.getPixel(i, centerJ)
				&& stateCount[0] <= maxCount) {
			stateCount[0]++;
			i--;
		}
		if (stateCount[0] > maxCount) {
			return Float.NaN;
		}

		// Count down from center
		i = startI + 1;
		while (i < maxI && image.getPixel(i, centerJ)) {
			stateCount[2]++;
			i++;
		}
		if (i == maxI) {
			return Float.NaN;
		}
		while (i < maxI && !image.getPixel(i, centerJ)
				&& stateCount[3] < maxCount) {
			stateCount[3]++;
			i++;
		}
		if (i == maxI || stateCount[3] >= maxCount) {
			return Float.NaN;
		}
		while (i < maxI && image.getPixel(i, centerJ)
				&& stateCount[4] < maxCount) {
			stateCount[4]++;
			i++;
		}
		if (stateCount[4] >= maxCount) {
			return Float.NaN;
		}
		if (checkRatios(stateCount)) {
			return estimateCenter(stateCount, i);
		}
		return Float.NaN;
	}

	private float checkCrossHorizontal(int startJ, int centerI, int maxCount) {
		BinaryImage image = this.image;

		int maxJ = image.getWidth();
		int[] stateCount = new int[5];

		int j = startJ;
		while (j >= 0 && image.getPixel(centerI, j)) {
			stateCount[2]++;
			j--;
		}
		if (j < 0) {
			return Float.NaN;
		}
		while (j >= 0 && !image.getPixel(centerI, j)
				&& stateCount[1] <= maxCount) {
			stateCount[1]++;
			j--;
		}
		if (j < 0 || stateCount[1] > maxCount) {
			return Float.NaN;
		}
		while (j >= 0 && image.getPixel(centerI, j)
				&& stateCount[0] <= maxCount) {
			stateCount[0]++;
			j--;
		}
		if (stateCount[0] > maxCount) {
			return Float.NaN;
		}

		j = startJ + 1;
		while (j < maxJ && image.getPixel(centerI, j)) {
			stateCount[2]++;
			j++;
		}
		if (j == maxJ) {
			return Float.NaN;
		}
		while (j < maxJ && !image.getPixel(centerI, j)
				&& stateCount[3] < maxCount) {
			stateCount[3]++;
			j++;
		}
		if (j == maxJ || stateCount[3] >= maxCount) {
			return Float.NaN;
		}
		while (j < maxJ && image.getPixel(centerI, j)
				&& stateCount[4] < maxCount) {
			stateCount[4]++;
			j++;
		}
		if (stateCount[4] >= maxCount) {
			return Float.NaN;
		}
		if (checkRatios(stateCount)) {
			return estimateCenter(stateCount, j);
		}
		return Float.NaN;
	}

	protected final boolean confirmFinderPattern(int[] stateCount, int i, int j) {
		int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2]
				+ stateCount[3] + stateCount[4];
		float centerJ = estimateCenter(stateCount, j);
		float centerI = checkCrossVertical(i, (int) centerJ, stateCount[2]);
		if (!Float.isNaN(centerI)) {
			// Re-cross check
			centerJ = checkCrossHorizontal((int) centerJ, (int) centerI,
					stateCount[2]);
			if (!Float.isNaN(centerJ)) {
				float estimatedModuleSize = (float) stateCountTotal / 7.0f;
				boolean found = false;
				for (int k = 0; k < listPoint.size(); k++) {
					PatternPoint temp = new PatternPoint(centerI, centerJ,
							estimatedModuleSize);
					if (listPoint.get(k).equals(temp)) {
						listPoint.set(k, listPoint.get(k).combine(temp));
						found = true;
						break;
					}
				}
				if (!found) {
					listPoint.add(new PatternPoint(centerI, centerJ,
							estimatedModuleSize));
				}
				return true;
			}
		}
		return false;
	}

	class MatchedCount implements Comparator<PatternPoint> {
		@Override
		public int compare(PatternPoint p1, PatternPoint p2) {
			return -(p1.getCount() - p2.getCount());
		}
	}

	class Ascending implements Comparator<PatternPoint> {
		@Override
		public int compare(PatternPoint p1, PatternPoint p2) {
			return (int) (p1.getY() - p2.getY());
		}
	}
}
